package com.company.并查集;

import java.util.HashMap;
import java.util.PriorityQueue;

public class Leet2580 {
    public int countWays(int[][] ranges) {
        //合并有交集的；计数m
        int m= ranges.length;
        //加入hashmap，把start相等的合并
        HashMap<Integer,Integer>map=new HashMap<>();
        //堆 所有start加入小根堆中
        PriorityQueue<Integer>pq=new PriorityQueue<>();
        for (int i = 0; i < ranges.length; i++) {
            int start=ranges[i][0];
            int end=ranges[i][1];
            if(map.containsKey(start)){
                m--;
                if(map.get(start)<end){
                    map.put(start,end);
                }
            }else{
                map.put(start,end);
                pq.offer(start);
            }
        }
        //取一个start，用end继续取，换end继续
        while (!pq.isEmpty()){
            int e=map.get(pq.poll());//当前组最大的end
            while (!pq.isEmpty()){
                int start=pq.peek();
                int end=map.get(start);
                if(e>=start){
                    m--;
                    e=end>e?end:e;
                    pq.poll();
                }else{
                    break;
                }
            }
        }
        //二的m次方取余返回
        int asw=1;
        for (int i = m; i > 0; i--) {
            asw=asw*2%1_000_000_007;
        }
        return asw;
    }
}
